{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Choose Edges to Maximize Score in a Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxScore"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #选择边来最大化树的得分"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个&nbsp;<strong>加权&nbsp;</strong>树，由 <code>n</code> 个节点组成，从 <code>0</code> 到 <code>n - 1</code>。</p>\n",
    "\n",
    "<p>该树以节点 0 为&nbsp;<strong>根</strong>，用大小为 <code>n</code> 的二维数组 <code>edges</code> 表示，其中 <code>edges[i] = [par<sub>i</sub>, weight<sub>i</sub>]</code> 表示节点 <code>par<sub>i</sub></code> 是节点 <code>i</code>&nbsp;的&nbsp;<strong>父&nbsp;</strong>节点，它们之间的边的权重等于 <code>weight<sub>i</sub></code>。因为根结点&nbsp;<strong>没有&nbsp;</strong>父结点，所以有 <code>edges[0] = [-1, -1]</code>。</p>\n",
    "\n",
    "<p>从树中选择一些边，使所选的两条边都不&nbsp;<strong>相邻</strong>，所选边的权值之 <strong>和</strong> 最大。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>返回<em>所选边的&nbsp;<strong>最大&nbsp;</strong>和。</em></p>\n",
    "\n",
    "<p><strong>注意</strong>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以&nbsp;<strong>不选择&nbsp;</strong>树中的任何边，在这种情况下权值和将为 <code>0</code>。</li>\n",
    "\t<li>如果树中的两条边 <code>Edge<sub>1</sub></code> 和 <code>Edge<sub>2</sub></code> 有一个&nbsp;<strong>公共&nbsp;</strong>节点，它们就是&nbsp;<strong>相邻&nbsp;</strong>的。\n",
    "\t<ul>\n",
    "\t\t<li>换句话说，如果 <code>Edge<sub>1</sub></code>连接节点 <code>a</code> 和 <code>b</code>, <code>Edge<sub>2</sub></code> 连接节点 <code>b</code> 和 <code>c</code>，它们是相邻的。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/16/treedrawio.png\" style=\"width: 271px; height: 221px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> edges = [[-1,-1],[0,5],[0,10],[2,6],[2,4]]\n",
    "<strong>输出:</strong> 11\n",
    "<strong>解释:</strong> 上面的图表显示了我们必须选择红色的边。\n",
    "总分是 5 + 6 = 11.\n",
    "可以看出，没有更好的分数可以获得。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/08/17/treee1293712983719827.png\" style=\"width: 221px; height: 181px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> edges = [[-1,-1],[0,5],[0,-6],[0,7]]\n",
    "<strong>输出:</strong> 7\n",
    "<strong>解释:</strong> 我们选择权值为 7 的边。\n",
    "注意，我们不能选择一条以上的边，因为所有的边都是彼此相邻的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == edges.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>par<sub>0</sub> == weight<sub>0</sub> == -1</code></li>\n",
    "\t<li><code>i &gt;= 1</code>&nbsp;时&nbsp;<code>0 &lt;= par<sub>i</sub> &lt;= n - 1</code>&nbsp;。</li>\n",
    "\t<li><code>par<sub>i</sub> != i</code></li>\n",
    "\t<li><code>i &gt;= 1</code>&nbsp;时&nbsp;<code>-10<sup>6</sup> &lt;= weight<sub>i</sub> &lt;= 10<sup>6</sup></code> 。</li>\n",
    "\t<li><code>edges</code> 表示有效的树。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [choose-edges-to-maximize-score-in-a-tree](https://leetcode.cn/problems/choose-edges-to-maximize-score-in-a-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [choose-edges-to-maximize-score-in-a-tree](https://leetcode.cn/problems/choose-edges-to-maximize-score-in-a-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-1,-1],[0,5],[0,10],[2,6],[2,4]]', '[[-1,-1],[0,5],[0,-6],[0,7]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values) -> int:\n",
    "        start_value = values[0]\n",
    "        location = 0\n",
    "        max_value = start_value + location\n",
    "        for i in range(1, len(values)):\n",
    "            temp_value = start_value + location + values[i] - i\n",
    "            if temp_value > max_value:\n",
    "                max_value = temp_value\n",
    "            if start_value + location < values[i] + i:\n",
    "                start_value = values[i]\n",
    "                location = i\n",
    "\n",
    "        return max_value\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        N = len(values)\n",
    "        p = values[0]\n",
    "        ans = 0\n",
    "        for i in range(1, N):\n",
    "            ans = max(ans, p+values[i]-i)\n",
    "            p = max(p, values[i]+i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre = values[0]\n",
    "        res = -10000\n",
    "        for i in range(1, len(values)):\n",
    "            res = max(res, values[i] + pre - 1)\n",
    "            pre = max(pre - 1, values[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre_max = values[0]\n",
    "        res = 0\n",
    "        for index in range(1, len(values)):\n",
    "            value = values[index]\n",
    "            res = max(res, value - index + pre_max)\n",
    "            if pre_max <= value+index:\n",
    "                pre_max = value+index\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "\n",
    "        max_v = 0\n",
    "        mx = values[0]\n",
    "        for j in range(1, n):\n",
    "            max_v = max(max_v, mx + values[j] - j)\n",
    "\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return max_v"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        maxValue = 0\n",
    "        preMax = values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            val = preMax + values[i] - i\n",
    "            maxValue = max(maxValue, val)\n",
    "            preMax = max(values[i] + i, preMax)\n",
    "        return maxValue"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "      ans, dp = 0, values[0]\n",
    "      for i in range(1, len(values)):\n",
    "        dp -= 1\n",
    "        ans, dp = max(ans, dp + values[i]), max(dp, values[i])\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''给你一个正整数数组 values,其中values[i] 表示第i个观光景点的评分，并且两个景点 i和j之间的距离为j-i。\n",
    "一对景点（i < j）组成的观光组合的得分为 values[i] + values[j] + i - j ，\n",
    "也就是景点的评分之和减去它们两者之间的距离。返回一对观光景点能取得的最高分。'''\n",
    "'''需要注意的是，一对景点之间的距离是个迷惑项，(values[i]+i)+(values[j]-j)才是正确的思路，\n",
    "通过一次遍历，我们可以预先取得下标为[0,j)和j的结点的分数,进而我们可以以O(N)的时间复杂度完成算法设计'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef maxScoreSightseeingPair(self, values: list[int]) -> int:\n",
    "\t\tmaxScored = values[0] + 0\n",
    "\t\tans = 0\n",
    "\t\tfor j in range(1, len(values)):\n",
    "\t\t\tans = max(ans, maxScored + values[j] - j)\n",
    "\t\t\tmaxScored = max(maxScored, values[j] + j)\n",
    "\t\treturn ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values) -> int:\n",
    "        # values[i] + values[j] + i - j = \n",
    "        # (values[i] + i) + (values[j] - j)\n",
    "        \n",
    "        max_value_i_plus_i = 0\n",
    "        max_score = 0\n",
    "        \n",
    "        for j, value in enumerate(values): \n",
    "            max_score = max(max_score, max_value_i_plus_i + value - j)\n",
    "            max_value_i_plus_i = max(max_value_i_plus_i, value + j)\n",
    "            \n",
    "        return max_score\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = -1\n",
    "        m1 = values[0] + 0\n",
    "        for i in range(1, len(values)):\n",
    "            res = max(res, m1 + values[i] - i)\n",
    "            m1 = max(m1, values[i] + i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        last = values[0]\n",
    "        ans = -inf\n",
    "        n = len(values)\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,values[i]-i+last)\n",
    "            last = max(last,values[i]+i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_max = values[0] + 0\n",
    "        for j in range(1, len(values)):\n",
    "            res = max(res, pre_max + values[j] - j)\n",
    "            pre_max = max(pre_max, values[j] + j)\n",
    "        return res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        pre_max = values[0]\n",
    "        res = 0\n",
    "        for index in range(1, len(values)):\n",
    "            value = values[index]\n",
    "            res = max(res, value - index + pre_max)\n",
    "            if pre_max <= value+index:\n",
    "                pre_max = value+index\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        a, b = 0, 1\n",
    "        c = values[a] + values[b] - (b - a) # 初始化答案\n",
    "        while b < n:\n",
    "            s = values[a] + values[b] - (b - a) # 计算当前观光组合得分s\n",
    "            c = max(c, s)\n",
    "            if values[a] + a < values[b] + b: # 移动指针的条件判断\n",
    "                a = b\n",
    "                b += 1\n",
    "            else:\n",
    "                b += 1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        a = values[0]-1\n",
    "        m = values[1]+a\n",
    "\n",
    "        for i in range(2,len(values)):\n",
    "            a = max(a - 1, values[i-1]-1)\n",
    "            m = max(values[i]+a,m)\n",
    "\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        dp = [0 for _ in range(n)]\n",
    "        for i in range(1, n):\n",
    "            dp[i] = max((dp[i - 1] + values[i] - values[i - 1] - 1), values[i] + values[i - 1] - 1)\n",
    "        return max(dp)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        ans, max_val = values[0], values[0]\n",
    "        for j in range(1, n):\n",
    "            ans = max(ans, max_val + values[j] - j)\n",
    "            max_val = max(max_val, values[j] + j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        left=0\n",
    "        max_=float('-inf')\n",
    "        for i in range(1,len(values)):\n",
    "            max_=max(max_,values[left]+values[i]+left-i)\n",
    "            if values[i]+i>values[left]+left:\n",
    "                left=i\n",
    "        return max_"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        left=values[0]\n",
    "        res=-1\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,left+values[i]-i)\n",
    "            left=max(left,values[i]+i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # (A[i] + i) + (A[j] - j)\n",
    "        if len(values) < 2:\n",
    "            return 0\n",
    "        ans = float('-inf')\n",
    "        mx = 0\n",
    "        for i in range(len(values)):\n",
    "            ans = max(ans, mx + values[i] - i)\n",
    "            mx = max(mx, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n=len(values)\n",
    "        output=float(\"-inf\")\n",
    "        pre_max=values[0]+0\n",
    "        for j in range(1,n):\n",
    "            output=max(output,pre_max+values[j]-j)\n",
    "            pre_max=max(pre_max,values[j]+j)\n",
    "        return output"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_i = values[0] + 0  # 初始化最大的 values[i] + i 值\n",
    "        max_score = 0  # 初始化最高得分\n",
    "        for j in range(1, len(values)):\n",
    "            # 计算可能的最高得分\n",
    "            max_score = max(max_score, max_i + values[j] - j)\n",
    "            # 更新最大的 values[i] + i 值\n",
    "            max_i = max(max_i, values[j] + j)\n",
    "        return max_score\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans,mx=0,values[0]\n",
    "        for j in range(1,len(values)):\n",
    "            ans=max(ans,mx+values[j]-j)\n",
    "            mx=max(mx,values[j]+j)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = values[0]\n",
    "        ans = 0\n",
    "        for j in range(1, n):\n",
    "            ans = max(ans, values[j] - j + mx)\n",
    "            mx = max(mx, values[j] + j)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans, premax = 0, values[0]\n",
    "        for i in range(1, len(values)):\n",
    "            ans = max(ans, premax + values[i] - i)\n",
    "            premax = max(premax, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # * 遍历\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = values[0] + 0\n",
    "        \n",
    "        for j in range(1, len(values)):\n",
    "            ans = max(ans, mx + values[j] - j)\n",
    "            # 边遍历边维护\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_score = 0\n",
    "        max_i = values[0]\n",
    "        for j in range(1, len(values)):\n",
    "            max_score = max(max_score, max_i + values[j] - j)\n",
    "            max_i = max(max_i, values[j] + j)\n",
    "        return max_score"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        tmp = values[0]\n",
    "\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,tmp+values[i]-i)\n",
    "            tmp = max(tmp,values[i]+i)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        buff = values[0] # 初始buff\n",
    "        ans = 0\n",
    "        for j in range(1, len(values)):\n",
    "        # 随着时间推移，buff的效力不断减少\n",
    "        # 初始效力为某个A[i], i < j\n",
    "        # 随时间减少的效力正好为 j - i\n",
    "        # 因此当前buff的剩余效力恰为 A[i] + i - j\n",
    "            buff -= 1\n",
    "            # 根据当前buff默默算一下自己的战斗力（战5渣..)\n",
    "            ans = max(ans, values[j] + buff)\n",
    "            # 看看当前buff剩余效力有没有刷新buff好，没有则刷新buff\n",
    "            buff = max(buff, values[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        pre = -inf\n",
    "        for x in values:\n",
    "            ans = max(ans, pre + x)\n",
    "            pre = max(pre, x)\n",
    "            pre -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        import sortedcontainers\n",
    "        res, l = 0, sortedcontainers.SortedList()\n",
    "        for i in range(len(values)): l.add(values[i]-i)\n",
    "        for i in range(len(values)-1):\n",
    "            l.discard(values[i]-i)\n",
    "            res = max(res, values[i]+i+l[-1])\n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        stack = []\n",
    "        ans = -inf\n",
    "        heappush(stack,-values[0])\n",
    "        n = len(values)\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,values[i]-i-stack[0])\n",
    "            heappush(stack,-values[i]-i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        mx = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,mx+values[i]-i)\n",
    "            mx = max(mx,values[i]+i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = values[0]\n",
    "        ans = [0] * n\n",
    "        for j in range(1, n):\n",
    "            ans[j] = values[j] - j + mx\n",
    "            mx = max(mx, values[j] + j)\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_value = values[0] + values[1] - 1\n",
    "        pre_max = max(values[0]-1, values[1])\n",
    "        for i in range(2, len(values)):\n",
    "            pre_max-=1\n",
    "            max_value = max(max_value, pre_max+values[i])\n",
    "            pre_max = max(pre_max, values[i])\n",
    "        return max_value"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        for i in range(len(values)):\n",
    "            values[i]=values[i]-i\n",
    "        res=0\n",
    "        mx=values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,mx+values[i])\n",
    "            mx=max(mx,values[i]+2*i)\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        for i in range(len(values)):\n",
    "            values[i]=values[i]-i\n",
    "        res=0\n",
    "        mx=values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res=max(res,mx+values[i])\n",
    "            mx=max(mx,values[i]+2*i)\n",
    "        return res    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        imax = values[0]\n",
    "        res = imax + values[1] - 1\n",
    "        for j in range(2, len(values)):\n",
    "            if (s := values[j-1] + j - 1) > imax:\n",
    "                imax = s\n",
    "            if (s := imax + values[j] - j) > res:\n",
    "                res = s\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\r\n",
    "        ans = 0\r\n",
    "        mx = values[0] + 0\r\n",
    "        for j in range(1, len(values)):\r\n",
    "            ans = max(ans, mx + values[j] - j)\r\n",
    "            mx = max(mx, values[j] + j)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        max_pre = values[0]\n",
    "        res = 0\n",
    "        for i in range(1, n):\n",
    "            res = max(res, values[i] - i + max_pre)\n",
    "            max_pre = max(max_pre, values[i] + i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        res = values[0] + values[1] - 1\n",
    "        dp = res\n",
    "        for i in range(2, n):\n",
    "            dp = max(dp + values[i] - values[i-1] - 1, values[i] + values[i-1] -1)\n",
    "            res = max(res, dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans=0\n",
    "        maxValue=0\n",
    "        for i in range(len(values)):\n",
    "            ans=max(ans,maxValue+values[i]-i)\n",
    "            maxValue=max(maxValue,values[i]+i)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        mx=values[0]\n",
    "        ans=0\n",
    "        for j in range(1,len(values)):\n",
    "            cur=values[j]-j\n",
    "            ans=max(ans,mx+cur)\n",
    "            mx=max(mx,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, A: List[int]) -> int:\n",
    "        buff=A[0]\n",
    "        ans=0\n",
    "        for j in range(1,len(A)):\n",
    "            buff-=1\n",
    "            ans=max(ans,buff+A[j])\n",
    "            buff=max(buff,A[j])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        a = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            a -= 1\n",
    "            ans = max(ans,values[i] + a)\n",
    "            a = max(a,values[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # k = values[i]+i + (values[j]-j)\n",
    "        n = len(values)\n",
    "        ans,mx = 0,values[0]+0\n",
    "        for j in range(1,n):\n",
    "            ans = max(ans,mx+values[j]-j)\n",
    "            mx = max(mx,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        a=values[0]+values[1]-1\n",
    "        b=max(values[0],values[1]+1)\n",
    "        for i in range(2,len(values)):\n",
    "            if (s:=b+values[i]-i)>a:\n",
    "                a=s\n",
    "            if (s:=values[i]+i)>b:\n",
    "                b=s\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        # j=1,初始化res[1],imax[1]\n",
    "        # score = V[i]+V[j]+i-j\n",
    "        res=values[0]+values[1]+0-1\n",
    "        imax=max(values[0]+0,values[1]+1)\n",
    "        for j in range(2,len(values)):\n",
    "            # walrus operator\n",
    "            if (tmp:=values[j-1]+j-1)>imax:\n",
    "                imax=tmp\n",
    "            if (tmp:=imax+values[j]-j)>res:\n",
    "                res=tmp\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        mtv = values[0]\n",
    "        mti = 0\n",
    "        ans = 0\n",
    "        for i in range(1,len(values)):\n",
    "            ans = max(mtv + values[i] - i + mti, ans)\n",
    "            if values[i] > mtv - i + mti:\n",
    "                mtv = values[i]\n",
    "                mti = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = 0\n",
    "        mx = values[0] + 0\n",
    "        \n",
    "        for j in range(1, len(values)):\n",
    "            ans = max(ans, mx + values[j] - j)\n",
    "            # 边遍历边维护\n",
    "            mx = max(mx, values[j] + j)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        premax = values[0] + 0\n",
    "        for j in range(1, len(values)):\n",
    "            res = max(res, values[j] - j + premax)\n",
    "            premax = max(premax, values[j] + j)\n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        '''\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        for i in range(n-1):\n",
    "            for j in range(i+1,n):\n",
    "                if values[i] + values[j] + i - j > ans:\n",
    "                    ans = values[i] + values[j] + i - j\n",
    "        return ans\n",
    "        '''\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        maxSightseeingIndex = values[0] + 0\n",
    "        for i in range(1,n):\n",
    "            ans = max(ans,maxSightseeingIndex + values[i] - i)\n",
    "            maxSightseeingIndex = max(values[i] + i,maxSightseeingIndex)\n",
    "            #print(ans, maxSightseeingIndex)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        dp = values[0]\n",
    "        ans = 0\n",
    "        for i in range(1,len(values)):\n",
    "            dp -= 1\n",
    "            ans = max(dp + values[i], ans)\n",
    "            if values[i] > dp:\n",
    "                dp = values[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        if len(values) < 2:\n",
    "            return -1\n",
    "        left = values[0]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(1, len(values), 1):\n",
    "            ans = max(ans, left + values[i] - i)\n",
    "            left = max(left, values[i] + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        pre_imax = 0\n",
    "        for j in range(1, len(values)):\n",
    "            pre_imax = max(pre_imax, (values[j-1]+j-1))\n",
    "            res = max(res, pre_imax+values[j]-j)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        max_i = 0\n",
    "        n = len(values)\n",
    "        ans = 0\n",
    "        for j in range(n):\n",
    "            ans = max(ans,values[j]-j+max_i)\n",
    "            max_i = max(max_i,values[j]+j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "\n",
    "        n = len(values)\n",
    "        candidate = values[-1] #= []\n",
    "        res = 0\n",
    "        for i in range(n-2, -1, -1):\n",
    "            # 先遍历candidates 他是后面可能更高的组合,\n",
    "            # candidates 不用记住值，遍历后直接减1就行了，\n",
    "            # 当前元素加入candidates后 所有小于x的人都不用看了 其实是单调栈吧\n",
    "            # x ... 56 这56是一个地位\n",
    "            \n",
    "            # for j, c in enumerate(candidates):\n",
    "            #     res = max(res, values[i] + candidates[j])\n",
    "            #     candidates[j] -= 1\n",
    "            #     if candidates[i] == 0\n",
    "            candidate -= 1\n",
    "            res = max(res, values[i] + candidate)\n",
    "            candidate = max(candidate, values[i])\n",
    "        return res\n",
    "\n",
    "\n",
    "            # 再过滤candidates"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        values[i] + values[j] + i - j\n",
    "        (values[i] + i) + values[j] - j\n",
    "        维护values[i] + i最大值，枚举答案 max(left + right)\n",
    "    '''\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        ans = left = 0\n",
    "        for i, x in enumerate(values):\n",
    "            ans = max(ans, left + x - i)\n",
    "            left = max(left, x + i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        res = 0\n",
    "        left = values[0]\n",
    "        for i in range(1,len(values)):\n",
    "            res = max(res,values[i] - i + left)\n",
    "            left = max(left,values[i] + i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        n = len(values)\n",
    "        mx = [0]*n\n",
    "        mx[0] = values[0]\n",
    "        ans = [0] * n\n",
    "        for j in range(1, n):\n",
    "            mx[j] = max(mx[j-1], values[j] + j)\n",
    "            ans[j] = values[j] - j + mx[j-1]\n",
    "        return max(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScoreSightseeingPair(self, values: List[int]) -> int:\n",
    "        zu = [0]*len(values)\n",
    "        for i in range(len(values)):\n",
    "            zu[i] = values[i]-i \n",
    "        max_index = [0]*len(values)\n",
    "        max_index[-1] = len(values) - 1 \n",
    "        for i in range(len(values)-2,-1,-1):\n",
    "            if zu[i] > zu[max_index[i+1]]:\n",
    "                max_index[i] = i \n",
    "            else:\n",
    "                max_index[i] = max_index[i+1]\n",
    "        res = -inf\n",
    "        for i in range(len(values)-1):\n",
    "            res = max(res,i - max_index[i+1] + values[i] + values[max_index[i+1]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #有向边--> pairi到i\n",
    "        #还原，对所选的边进行还原，到也不麻烦，记录节点是否被选即可\n",
    "        #没有很好的还原，这一题对于不同子树的考量并不相同,并不是考虑点，而是考虑边了\n",
    "        n=len(edges)\n",
    "        g=[[] for _ in range(n)]\n",
    "        for x,(y,_) in enumerate(edges):\n",
    "            if y==-1:continue\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def dfs(x:int,fa:int)->(int,int): #选择一条端点起点是x的边，不选择端点起点是x的边      \n",
    "            s1,s2=0,0 #s1代表将x选择\n",
    "            max_diff=-inf\n",
    "            g1,g2=0,0\n",
    "            for y in g[x]:\n",
    "                if y==fa:\n",
    "                    continue\n",
    "                f1,f2=dfs(y,x)\n",
    "                #选择了x，那么y一定不能选\n",
    "                s1=edges[y][1]+f2\n",
    "                s2=max(f1,f2)\n",
    "                max_diff=max(max_diff,s1-s2)\n",
    "                g2+=s2\n",
    "\n",
    "            return g2+max_diff,g2\n",
    "        return max(dfs(0,-1))\n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #树上DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            #cur用来保存只选一条边时,最大的差值\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点(向下考虑),那它的孩子节点可以选一个连接,其他不能选。\n",
    "            #dp[1]表示选当前节点(向下考虑),那它的孩子节点一个都不能选\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        dic = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dic[edges[i][0]].append(i)\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not dic[root]:\n",
    "                return edges[root][1],0\n",
    "            sumn = 0\n",
    "            diff = 0\n",
    "            for k,child in enumerate(dic[root]):\n",
    "                tmp1,tmp2 = dfs(child)\n",
    "                sumn+=tmp2\n",
    "                if tmp1-tmp2>diff:\n",
    "                    diff=tmp1-tmp2\n",
    "            res = max(res,edges[root][1]+sumn,sumn+diff)\n",
    "            return edges[root][1]+sumn,sumn+diff\n",
    "        print(dfs(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点\n",
    "            #dp[1]表示选当前节点(向下考虑)\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #树上DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            #cur用来保存只选一条边时,最大的差值\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点(向父节点考虑),那它的孩子节点可以选一个连接,其他不能选。\n",
    "            #dp[1]表示选当前节点(向父节点考虑),那它的孩子节点一个都不能选\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return dfs(0)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        dic = [[] for _ in range(n)]\n",
    "        for i in range(1,n):\n",
    "            dic[edges[i][0]].append(i)\n",
    "        res = 0\n",
    "        def dfs(root):\n",
    "            nonlocal res\n",
    "            if not dic[root]:\n",
    "                return edges[root][1],0\n",
    "            sumn = 0\n",
    "            diff = 0\n",
    "            for k,child in enumerate(dic[root]):\n",
    "                tmp1,tmp2 = dfs(child)\n",
    "                sumn+=tmp2\n",
    "                if tmp1-tmp2>diff:\n",
    "                    diff=tmp1-tmp2\n",
    "            res = max(res,edges[root][1]+sumn,sumn+diff)\n",
    "            return edges[root][1]+sumn,sumn+diff\n",
    "        print(dfs(0))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        #树上DP\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            #cur用来保存只选一条边时,最大的差值\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点(向下考虑)\n",
    "            #dp[1]表示选当前节点(向下考虑)\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n=len(edges)\n",
    "        graph=[[] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            if edges[i]==[-1,-1]:\n",
    "                continue\n",
    "            graph[edges[i][0]].append((i,edges[i][1]))\n",
    "        #初始化完成\n",
    "        def dfs(x):\n",
    "            #叶子节点\n",
    "            if not graph[x]:\n",
    "                return [0,0]\n",
    "            dp=[0,0]\n",
    "            cur=0\n",
    "            #dp[0]表示不选当前节点\n",
    "            #dp[1]表示选当前节点(向下考虑)\n",
    "            for y,v in graph[x]:\n",
    "                nex=dfs(y)\n",
    "                dp[1]+=nex[0]\n",
    "                dp[0]+=nex[0]\n",
    "                cur=max(cur,nex[1]-nex[0]+v)\n",
    "            dp[0]+=cur\n",
    "            return dp\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        n=len(edges)\n",
    "        for i,(p,w) in enumerate(edges):\n",
    "            g[p].append((i,w))\n",
    "        def dfs(k):\n",
    "            rx,rn=0,0#这个点相邻的选了， 这个点相邻的没选\n",
    "            t=[]\n",
    "            for nk,w in g[k]:\n",
    "                x,n=dfs(nk)\n",
    "                t.append((x,n,w))\n",
    "                rn+=x\n",
    "            rx=rn\n",
    "            for x,n,w in t:\n",
    "                rx=max(rx,rn-x+n+w,rn-x+n)\n",
    "            return rx,rn\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        n=len(edges)\n",
    "        for i,(p,w) in enumerate(edges):\n",
    "            g[p].append((i,w))\n",
    "        def dfs(k):\n",
    "            re_use,re_no_use=0,0#这个点相邻的选,这个点相邻的没选\n",
    "            t=[]\n",
    "            for nk,w in g[k]:\n",
    "                u,n=dfs(nk)\n",
    "                t.append((u,n,w))\n",
    "                #累加所有下面的选了的\n",
    "                re_no_use+=u\n",
    "            #初始化选了的值，至少要比都没选的高\n",
    "            re_use=re_no_use\n",
    "            for u,n,w in t:\n",
    "                #枚举选了的话 选那一条边 注意W可能为负数\n",
    "                re_use=max(re_use,re_no_use-u+n+w,re_no_use-u+n)\n",
    "            return re_use,re_no_use\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g=defaultdict(list)\n",
    "        n=len(edges)\n",
    "        for i,(p,w) in enumerate(edges):\n",
    "            g[p].append((i,w))\n",
    "        def dfs(k):\n",
    "            re_use,re_no_use=0,0#这个点相邻的选,这个点相邻的没选\n",
    "            t=[]\n",
    "            for nk,w in g[k]:\n",
    "                u,n=dfs(nk)\n",
    "                t.append((u,n,w))\n",
    "                #累加所有下面的选了的\n",
    "                re_no_use+=u\n",
    "            #初始化选了的值，至少要比都没选的高\n",
    "            re_use=re_no_use\n",
    "            for u,n,w in t:\n",
    "                #枚举选了的话 选那一条边 注意W可能为负数\n",
    "                re_use=max(re_use,re_no_use-u+n+w,re_no_use-u+n)\n",
    "            return re_use,re_no_use\n",
    "        return max(dfs(0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        tree = collections.defaultdict(list)\n",
    "        n = len(edges)\n",
    "        for i in range(1, n):\n",
    "            tree[edges[i][0]].append([i, edges[i][1]])\n",
    "        \n",
    "        def dfs(i):\n",
    "            if not tree[i]:\n",
    "                return 0, 0\n",
    "            \n",
    "            can, cannot = [], []\n",
    "            for nex, val in tree[i]:\n",
    "                nexCan, nexCannot = dfs(nex)\n",
    "                can.append(max(nexCan, nexCannot))\n",
    "                cannot.append(nexCan + val - can[-1])\n",
    "            \n",
    "            ans = sum(can)        \n",
    "            return ans, ans + max(cannot)\n",
    "\n",
    "        can, cannot = dfs(0)\n",
    "        return max(can, cannot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        tree = collections.defaultdict(list)\n",
    "        n = len(edges)\n",
    "        for i in range(1, n):\n",
    "            tree[edges[i][0]].append([i, edges[i][1]])\n",
    "        \n",
    "        def dfs(i):\n",
    "            if not tree[i]:\n",
    "                return 0, 0\n",
    "            \n",
    "            can, cannot = [], []\n",
    "            for nex, val in tree[i]:\n",
    "                nexCan, nexCannot = dfs(nex)\n",
    "                can.append(max(nexCan, nexCannot))\n",
    "                cannot.append(nexCan + val - can[-1])\n",
    "            \n",
    "            ans = sum(can)        \n",
    "            return ans, ans + max(cannot)\n",
    "\n",
    "        can, cannot = dfs(0)\n",
    "        return max(can, cannot)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        d = collections.defaultdict(dict)\n",
    "        for u, (v, w) in enumerate(edges):\n",
    "            if u != 0:\n",
    "                d[v][u] = w\n",
    "        \n",
    "        def dfs(u):\n",
    "            if not d[u]:\n",
    "                return 0, 0\n",
    "            w_ans = []\n",
    "            left_ans = []\n",
    "            right_ans = []\n",
    "            for v in d[u]:\n",
    "                w_ans.append(d[u][v])\n",
    "                left_value, right_value = dfs(v)\n",
    "                left_ans.append(left_value)\n",
    "                right_ans.append(right_value)\n",
    "            m = len(w_ans)\n",
    "            sum_left_ans = sum(left_ans)\n",
    "            sum_right_ans = sum(right_ans)\n",
    "            left_output = -float('inf')\n",
    "            right_output = sum_left_ans\n",
    "            for i in range(m):\n",
    "                left_output = max(left_output, w_ans[i] + right_ans[i] + sum_left_ans - left_ans[i])\n",
    "            left_output = max(left_output, right_output)\n",
    "            return left_output, right_output\n",
    "        return dfs(0)[0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 树形DP\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        # 多叉树的打家劫舍\n",
    "        # edges[i] = [parenti,weighti]\n",
    "        graph = collections.defaultdict(list) # key == node, val == children\n",
    "        for i, pair in enumerate(edges):\n",
    "            graph[pair[0]].append((i, pair[1]))\n",
    "\n",
    "        # 然后记忆化搜索，要么\n",
    "\n",
    "        @cache\n",
    "        def dfs(node): # 以node为根节点，看可以选择哪些值\n",
    "            maxVal = 0\n",
    "            # 选择了它，则不可以选择它的孩子，但可以选择它的孙子\n",
    "            cs = [0] # 加个哨兵0，防止sum求空列表\n",
    "            for child, weight in graph[node]:\n",
    "                cs.append(dfs(child))\n",
    "\n",
    "            tsum = sum(cs)\n",
    "            maxVal = max(maxVal, tsum) # 注意这里的边界处理，不选择任意一条边，只选择它们的孩子\n",
    "            for i, pair in enumerate(graph[node]):\n",
    "                child, weight = pair\n",
    "                g = 0 # 考虑它的孙子辈的总和\n",
    "                for grandson, w2 in graph[child]:\n",
    "                    g += dfs(grandson)      \n",
    "\n",
    "                maxVal = max(maxVal, weight + tsum - dfs(child) + g) # 总和减去不可选择的这条孩子的和\n",
    "\n",
    "            return maxVal \n",
    "        \n",
    "\n",
    "        return dfs(0)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        n = len(edges)\n",
    "        g = [[] for _ in range(n)]\n",
    "        for i, (a, b) in enumerate(edges[1:], 1):\n",
    "            g[a].append([i, b])\n",
    "\n",
    "        @cache\n",
    "        def f(node):\n",
    "            if not g[node]:\n",
    "                return 0, 0\n",
    "            a, b = 0, 0\n",
    "            res = 0\n",
    "            for nxt, w in g[node]:\n",
    "                res += max(f(nxt)[0], f(nxt)[1])\n",
    "            for nxt, w in g[node]:\n",
    "                b = max(b, res - max(f(nxt)[0], f(nxt)[1]) + w + f(nxt)[0])\n",
    "            return res, b \n",
    "        \n",
    "        return max(f(0))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        tree = [[] for _ in range(len(edges))]\n",
    "\n",
    "        for u, (fa, w) in enumerate(edges):\n",
    "            if fa == -1: continue\n",
    "            tree[fa].append((u, w))\n",
    "        \n",
    "        @cache\n",
    "        def treeDP(u, op):\n",
    "            dp0 = dp1 = 0\n",
    "            for v, w in tree[u]: dp1 += treeDP(v, 0)\n",
    "            if op: return dp1\n",
    "            for v, w in tree[u]: dp0 = max(dp0, dp1 - treeDP(v, 0) + treeDP(v, 1) + w)\n",
    "            return max(dp0, dp1)\n",
    "        \n",
    "        return treeDP(0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\r\n",
    "        n = len(edges)\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for i, [fa, w] in enumerate(edges):\r\n",
    "            if i == 0: continue\r\n",
    "            g[fa].append((i, w))\r\n",
    "            \r\n",
    "        @cache\r\n",
    "        def dfs(u, state):\r\n",
    "            # 叶子结点没有子节点 返回0\r\n",
    "            if not g[u]:\r\n",
    "                return 0\r\n",
    "            ans = res = 0\r\n",
    "            # 假如一条边都不选\r\n",
    "            for v, w in g[u]:\r\n",
    "                ans += dfs(v, False)\r\n",
    "            # 当前点已经被选过了，所以儿子一个都不能选\r\n",
    "            if state: return ans\r\n",
    "            # 当前点没被选中，那只能选一个儿子，并且其他儿子都不选\r\n",
    "            for v, w in g[u]:\r\n",
    "                res = max(res, ans - dfs(v, False) + dfs(v, True) + w)\r\n",
    "            return max(ans, res)\r\n",
    "        return dfs(0, False)\r\n",
    "        \r\n",
    "\r\n",
    "    def maxScore2(self, edges: List[List[int]]) -> int:\r\n",
    "        \"\"\"在树中选择一些边使得选出的边不相连，最大化边权之和\"\"\"\r\n",
    "\r\n",
    "        def dfs(cur: int, pre: int) -> Tuple[int, int]:\r\n",
    "            \"\"\"返回[选择连接父亲的边时子树最大价值, 不选择连接父亲的边时子树最大价值]\r\n",
    "\r\n",
    "            如果选到父亲的边,所有儿子都不能选\r\n",
    "            如果不选到父亲的边,所有儿子中选一个diff最大的\r\n",
    "            \"\"\"\r\n",
    "            res1, res2 = 0, 0\r\n",
    "            diff = [0]\r\n",
    "            for next in adjMap[cur]:\r\n",
    "                select, jump = dfs(next, cur)\r\n",
    "                res1, res2 = res1 + jump, res2 + jump\r\n",
    "                diff.append(select + adjMap[cur][next] - jump)\r\n",
    "\r\n",
    "            res2 += max(diff)\r\n",
    "            return res1, res2\r\n",
    "\r\n",
    "        adjMap = defaultdict(lambda: defaultdict(lambda: -inf))\r\n",
    "        for cur, (parent, weight) in enumerate(edges):\r\n",
    "            if parent == -1:\r\n",
    "                continue\r\n",
    "            adjMap[parent][cur] = weight\r\n",
    "\r\n",
    "        return max(0, dfs(0, -1)[1])  # 不连接虚拟根节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxScore(self, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, (x, y) in enumerate(edges):\n",
    "            g[x].append((i, y))\n",
    "        @cache\n",
    "        def f(x, flag):\n",
    "            if flag:\n",
    "                rnt = 0\n",
    "                for y, v in g[x]:\n",
    "                    rnt += f(y, False)\n",
    "            else:\n",
    "                rnt = 0\n",
    "                for y, v in g[x]:\n",
    "                    rnt += f(y, False)\n",
    "                for y, v in g[x]:\n",
    "                    t = v + f(y, True)\n",
    "                    for z, v in g[x]:\n",
    "                        if y != z:\n",
    "                            t += f(z, False)\n",
    "                    rnt = max(rnt, t)\n",
    "            return rnt\n",
    "                        \n",
    "        return f(0, False)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
